import java.util.Random;

public class Percolation
{
//	private PercolationStats[] point;
	private int[] id = null;
	private boolean[] isopened = null;
	private boolean isPercolation = false;
	private int[] size = null;
	int topPoint = 0;
//	int bottomPoint = 0;
	int Size = 0;
	public Percolation(int N)
	{
		if(N<=0)
			throw new java.lang.IllegalArgumentException();
		Size=N;
		//initialize the grid & virtual top point & bottom point
		id = new int[N*N +1];
		size = new int[N*N +1];
		isopened = new boolean[N*N+1];
		
		topPoint = N*N;
//		bottomPoint = N*N+1;
		for(int i=0; i<N*N+1; i++)
		{
			id[i] = i;
			isopened[i] = false;
			size[i] = 1;
		}
		isopened[topPoint] = true;
//		isopened[bottomPoint] = true;
		
	}
	public void open(int row, int col)
	{
//		if(row > Size || row < 1 || col > Size || col < 1)
//			throw new java.lang.IndexOutOfBoundsException();
		int index = getIndex(row, col);
		int tmpIndex = 0;
		if(!isopened[index])//connect it with adjacent open sites
		{
			isopened[index] = true;//open it
			if(row>1){
				tmpIndex = getIndex(row-1, col);
				if(isopened[tmpIndex]) //top is open
					union(index, tmpIndex);
			}
			else //connected to top Point
			{
				union(index, topPoint);
			}

			if(row<Size){
				tmpIndex = getIndex(row+1, col);
				if(isopened[tmpIndex]) //bottom is open
					union(index, tmpIndex);
			}
			else //connected to bottom Point
			{
				if(connected(index, topPoint))
					isPercolation = true;
			}

			if(col>1){
				tmpIndex = getIndex(row, col-1);
				if(isopened[tmpIndex]) //left is open
					union(index, tmpIndex);
			}

			if(col<Size){
				tmpIndex = getIndex(row, col+1);
				if(isopened[tmpIndex]) //right is open
					union(index, tmpIndex);
			}
		}
		return;
	}
	public boolean isOpen(int row, int col)
	{
		int index = getIndex(row, col);
		return (isopened[index]);
	}
	public boolean isFull(int row, int col)
	{
//		if(row > Size || row < 1 || col > Size || col < 1) 
//			throw new java.lang.IndexOutOfBoundsException();
		int index = getIndex(row, col);
		return(connected(topPoint, index));
	}
	public boolean percolates()
	{
		return isPercolation;
	}
	
	public static void main(String[] args)
	{
		Random rand = new Random();
		int N = 1000;
		int count = 0;
		int row = 0, col=0;
		
		Percolation perc = new Percolation(N);
		while(!perc.percolates())
		{
			row = rand.nextInt(N) +1;
			col = rand.nextInt(N) +1;
			if(!perc.isOpen(row, col))
			{
				perc.open(row, col);
				count ++;
			}
		}

        StdOut.println("threshold = "+(double)count / (double)(N*N));
	}
	

	private int getIndex(int row, int col)
	{
		if(row > Size || row < 1 || col > Size || col < 1) 
			throw new java.lang.IndexOutOfBoundsException();
		return (row-1)*Size + (col-1);
	}
	private int root(int p)
	{
		int i = p;
		int tmp = i;
		while(id[i] != i)//not root
		{
			tmp = id[id[i]];// upload root
			i = id[i];
			id[i] = tmp;
		}
		return i;
	}
	private void union(int p, int q)
	{
		int RP = root(p);
		int RQ = root(q);
		if(RP != RQ)
		{
			if(size[RP] < size[RQ])
			{
				id[RP] = RQ;
				size[RQ] += size[RP];
			}
			else
			{
				id[RQ] = RP;
				size[RP] += size[RQ];
			}
		}			
		return;
	}
	private boolean connected(int p, int q)
	{
		if(!isopened[p] || !isopened[q]) 
			return false;

		return (id[root(p)] == id[root(q)]);
	}
	private int count()
	{
		return Size;
	}
}